#define m 5 // B树的阶，暂设为5
typedef int keytype;
typedef int datatype;
typedef struct b_node
{
    int keynum;             //结点中关键码的个数，即结点的大小
    struct b_node *parent;  //指向双亲结点(上图未显示)
    keytype key[m];         //关键码向量, key[1].. key[m-1], 0分量未用
    datatype *eptr[m];      //记录指针向量, eptr[1].. eptr[m-1]   (上图未显示)
    struct b_node *nptr[m]; //子树指针向量nptr[0]..nptr[m-1]
} B_Node, *B_Tree;
typedef struct
{
    B_Node *pt; //指向找到的结点
    int i;      //在结点中的关键码序号，结点序号区[1…m]
    int tag;    // 1:查找成功，0:查找失败
} Result;       // B树的查找结果类型
#pragma region 【算法6 - 13】B 树上的查找
Result SearchBTree(B_Tree t, keytype kx)
{ //在m阶B树t上查找关键码kx，返回(pt,i,tag)
  //查找成功，特征值tag=1，指针pt所指结点中第i个关键码等于kx
  //失败，特征值tag=0，pt指出插入位置
    Result rs;
    B_Node *p, *q; //初始化，p指向待查结点，q指向p的双亲
    p = t;
    q = NULL;
    int i, found = 0;
    while (p && !found)
    {
        i = Search(p, kx); //在p->key[1…keynum]中查找kx,返回0->在比第一个键小的位置，其他->相应的键码位置，算法及代码略...
        if (i > 0 && p->key[i] == kx)
            found = 1; //找到
        else
        {
            q = p;
            p = p->nptr[i]; //在p->nptr[i-1]子树中查找
        }
    }
    rs.tag = found;
    if (!found)
        p = q; //查找不成功，返回kx的插入位置信息
    rs.pt = p;
    rs.i = i; //查找成功, 返回指向kx位置的信息
    return rs;
}
#pragma endregion

